package mytest.huaweiG; /**
 * Created by safe on 2017-03-26.
 */

import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * PriorityQueue + Dijkstra算法求单源最短路径
 *
 * 使用java类库中的PriorityQueue来实现，
 *
 *
 *
 */
public class DijKstra_set {
    private Graph gr;
    // 最短路径数组
    	static int[] dist;
    // S集合,代表着已经找到最短路径的结点
    private HashSet<Integer> s;
    // 映射集合
    private dist[] distArray;
    // 优先级队列
    private PriorityQueue<dist> pq;
    private int max = 1000000;


    /**
     * dist: 保存源结点至每个结点的最短路径
     * @author
     *
     */
    private class dist implements Comparable<dist> {

        int value;
        int index;

        public dist(int value, int index) {
            this.value = value;
            this.index = index;
        }

        @Override
        public int compareTo(dist o) {
            if (o.value < this.value) {
                return 1;
            } else if (o.value > this.value) {
                return -1;
            } else {
                return 0;
            }
        }

    }

/*    public static void main(String[] args) {



        long begin = System.currentTimeMillis();

        //djst();

        long end = System.currentTimeMillis();

        System.out.println(end - begin + "ms");
    }*/

    public static void initialize_Single_Source(Graph G,Node s) {
        //foreach vertex v in V[G]
                //do d[v]=INFINITE;
                   // pai[v]=NIL;
        //d[s]=0;
    }

    private static void BFS_By_Weight(Graph G,Node s){

    }

    /**
     * PriorityQueue + Dijkstra算法实现
     */
    private void djst(Graph gr, Node source) {
       int nodeCount=gr.getNodeCount();

        s = new HashSet<Integer>();
        pq = new PriorityQueue<dist>(nodeCount);
        distArray = new dist[nodeCount];
/*        tempNode = firstArray[1];
        for (int i = 2; i < nodeCount + 1; i ++) {
            HashMap<Integer, Integer> tempMap = tempNode.bandwidth ;
            if (tempMap.containsKey(i)) {
                dist d = new dist(tempMap.get(i), i);
                pq.offer(d);
                distArray[i] = d;
            } else {
                dist d = new dist(max, i);
                pq.offer(d);
                distArray[i] = d;
            }
        }
        s.add(1);*/

/*        while (s.size() < nodeCount) {

            dist d = pq.poll();
            int index = d.index;
            int value = d.value;

            s.add(index);

            // 用indx这个点去更新它的邻接点到开始点的距离
            HashMap<Integer, Integer> m = firstArray[index].bandwidth ;
            if (m == null) {
                continue;
            }
            Set<Integer> set = m.keySet();
            Iterator<Integer>it = set.iterator();
            while (it.hasNext()) {
                int num = it.next();
                if (num == 1) {
                    continue;
                }
                dist tempDist = distArray[num];
                if (m.get(num) + value < tempDist.value) {
                    pq.remove(tempDist);
                    tempDist.value = m.get(num) + value;
                    pq.offer(tempDist);
                    distArray[num] = tempDist;
                }
            }
        }

        for (int i = 2; i < nodeCount + 1; i ++) {
            System.out.println(distArray[i].value);
        }*/
    }

}
